package one2Ten;

import java.util.ArrayList;

/**
 * 递增数组的旋转数组的最小数字
 * Created by Wongy on 2018/3/12.
 */
public class Eight8 {
    private static int minNumberInRotateArray(int[] array) {
        if (array == null || array.length == 0)
            return 0;
        int left = 0;
        int right = array.length - 1;
        int mid = 0;

        //二分查找
        //排除顺序排列的可能
        while (array[left] >= array[right]) {
            if (right - left <= 1) {
                mid = right;
                break;
            }
            mid = (left + right) / 2;
            if (array[left] == array[mid] && array[mid] == array[right]) {
                if (array[left + 1] != array[right - 1]) {
                    mid = array[left + 1] < array[right - 1] ? left + 1 : right - 1;
                } else {
                    left++;
                    right--;
                }
            } else {
                if (array[left] <= array[mid]) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
        }
        return array[mid];
    }

    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        int[] array = {3, 4, 1, 2, 2};
        Integer number = minNumberInRotateArray(array);
        System.out.println(number);
        System.out.println("Eight8.main , 45 : " + 5 / 2);
    }
}
